package com.conjane.algo.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 删除最外层括号
 */
public class RemoveOuterParentheses {

    /**
     * 计算左右括号的个数，如果左右括号的数量相等，则算作为一个原语，
     * 得到的字符串放入到list中，最后遍历list，删除最外面的括号，
     * 拼接成新的字符串，返回结果。
     * @param s
     * @return
     */
    public static String remove(String s){
        int len = s.length();
        List<String> list = new ArrayList<>();
        int left = 0,right = 0,lastPosition = 0;
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '('){
                left++;
            }else if (c == ')'){
                right++;
            }

            if (left == right){
                String substring = s.substring(lastPosition, i + 1);
                list.add(substring);
                lastPosition = i + 1;
            }
        }

        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            String s1 = list.get(i);
            String subStr = s1.substring(1, s1.length() - 1);
            builder.append(subStr);
        }
        return builder.toString();
    }

    /**
     * 将括号放入栈中，然后做左右括号匹配
     * @param s
     * @return
     */
    public static String removePlus(String s){
        Stack<Character> stack = new Stack<>();
        StringBuilder builder = new StringBuilder();
        int lastPosition = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == '('){
                stack.push(c);
            }else if (c == ')'){
                stack.pop();
            }

            if (stack.isEmpty()){
                builder.append(s.substring(++lastPosition,i));
                lastPosition = i + 1;
            }
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        String s = "((a))(((b)(c)))((d))";
        String remove = removePlus(s);
        System.out.println(remove);
    }
}
